// https://leetcode.cn/problems/simplify-path/?envType=study-plan-v2&envId=top-interview-150

class Solution {
public:
    string simplifyPath(string path) {
        int index = 0;
        stack<string> dirs;
        int n = path.size();

        while (index < n) {
            if (path[index] == '/') {
                index++;
                continue;
            }
            
            string dir = "";
            while (index < n && path[index] != '/') {
                dir += path[index];
                index++;
            }

            if (dir == ".") {
                continue;
            } else if (dir == "..") {
                if (dirs.empty()) {
                    continue;
                } else {
                    dirs.pop();
                }
            } else {
                dirs.push(dir);
            }
        }

        string pathStr = "";
        while (!dirs.empty()) {
            string prefix = dirs.top();

            if (pathStr != "") {
                prefix += '/';
            }

            prefix += pathStr;
            pathStr = prefix;
            dirs.pop();
        }
        return "/" + pathStr;
    }
};